package com.zhugang.week07;

import java.util.ArrayList;
import java.util.List;

/**
 * @program algorithms
 * @description: pathSum
 * @author: chanzhugang
 * @create: 2022/07/22 23:49
 */
public class PathSum {

    /**
     * 剑指offer 34 二叉树中和为某一值的路径
     *
     * @param root
     * @param target
     * @return
     */

    private List<List<Integer>> result;

    public List<List<Integer>> pathSum(TreeNode root, int target) {
        // 根节点到叶子节点路径总和等于给定值的所有路径
        result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        dfs(root, target, new ArrayList<>(), 0);
        return result;
    }

    /**
     * @param root    根节点
     * @param sum     目标值
     * @param path    路径上的值
     * @param pathSum 路径上值的和
     */
    private void dfs(TreeNode root, int sum, List<Integer> path, int pathSum) {
        path.add(root.val);
        pathSum += root.val;
        if (root.left == null && root.right == null) {
            // 到了叶子节点
            if (pathSum == sum) {
                // 快照
                List<Integer> pathSnapshot = new ArrayList<>();
                pathSnapshot.addAll(path);
                result.add(pathSnapshot);
            }
            path.remove(path.size() - 1);
            return;
        }

        if (root.left != null) {
            dfs(root.left, sum, path, pathSum);

        }
        if (root.right != null) {
            dfs(root.right, sum, path, pathSum);
        }
        path.remove(path.size() - 1);
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}